﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 算法基本功.算法._0_数组._4_滑动数组
{
    internal class 最小覆盖子串
    {
        public string MinWindow(string s, string t)
        {
            //目标Dict
            Dictionary<char, int> need = new Dictionary<char, int>();
            //窗口Dict
            Dictionary<char, int> window = new Dictionary<char, int>();

            //快慢指针
            int left = 0, right = 0;
            //有多少种字符已满足条件
            int valid = 0;
            //当前窗口的起始索引 
            int start = 0;
            //记录当前窗口的长度
            int windowLength = int.MaxValue;

            //初始化目标Dict
            foreach (var c in t) {
                if (need.ContainsKey(c))
                {
                    need[c]++;
                }
                else {
                    need[c] = 1;
                }
            }


            //开启右滑动
            while (right < s.Length) { 
                //右指针滑动过程中添加的字符
                char c = s[right];
                right++;

                //如果找到了目标字符 添加到窗口之中
                if (need.ContainsKey(c)) {

                    if (window.ContainsKey(c))
                    {
                        window[c]++;
                    }
                    else {
                        window[c] = 1;
                    }

                    //每有一种字符满足条件的时候 就让valid标志+1
                    if (window[c] == need[c]) {
                        valid ++;
                    }
                }

                //当窗口已包含所有目标字符（valid等于目标字符种类数）时，尝试收缩左边界以寻找更短的有效子串
                while (valid == need.Count) {
                    //计算一下最小覆盖子串
                    int currentMinValue = right - left;
                    //更新一下起始索引与长度
                    if (currentMinValue < windowLength) {
                        start = left;
                        windowLength = currentMinValue;
                    }

                    //尝试缩小
                    char d = s[left];
                    left ++;

                    //如果不小心把满足条件的字符缩出去了 
                    if (need.ContainsKey(d)) {
                        //控制一下valid
                        if (window[d] == need[d]) {
                            valid--;
                        }
                        //因为可能存在一个字符有多个出现次数 因此默认让其对应数量-1
                        window[d] --;
                    }
                }
            
            }
            return windowLength == int.MaxValue ? "" : s.Substring(start, windowLength);
        }
    }
}
